{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Smooth Descent Periods of a Stock"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getDescentPeriods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #股票平滑下跌阶段的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>prices</code>&nbsp;，表示一支股票的历史每日股价，其中&nbsp;<code>prices[i]</code>&nbsp;是这支股票第&nbsp;<code>i</code>&nbsp;天的价格。</p>\n",
    "\n",
    "<p>一个 <strong>平滑下降的阶段</strong>&nbsp;定义为：对于&nbsp;<strong>连续一天或者多天</strong>&nbsp;，每日股价都比 <strong>前一日股价恰好少 </strong><code>1</code>&nbsp;，这个阶段第一天的股价没有限制。</p>\n",
    "\n",
    "<p>请你返回 <strong>平滑下降阶段</strong>&nbsp;的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>prices = [3,2,1,4]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>总共有 7 个平滑下降阶段：\n",
    "[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]\n",
    "注意，仅一天按照定义也是平滑下降阶段。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>prices = [8,6,7,7]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]\n",
    "由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>prices = [1]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>总共有 1 个平滑下降阶段：[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= prices[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-smooth-descent-periods-of-a-stock](https://leetcode.cn/problems/number-of-smooth-descent-periods-of-a-stock/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-smooth-descent-periods-of-a-stock](https://leetcode.cn/problems/number-of-smooth-descent-periods-of-a-stock/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1,4]', '[8,6,7,7]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self, n):\n",
    "        # C(n, 1) + .. + C(n, n)\n",
    "        return (1 + n) * n // 2\n",
    "\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        # 求连续下降为1的连续子串的长度\n",
    "        n = len(prices)\n",
    "        l = 0\n",
    "        ans = []\n",
    "        while l < n:\n",
    "            r = l\n",
    "            while r + 1 < n and (prices[r+1] - prices[r] == -1):\n",
    "                r += 1\n",
    "            ans.append(r - l + 1)\n",
    "            l = r + 1\n",
    "        res = 0\n",
    "        for item in ans:\n",
    "            res += self.help(item)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "\n",
    "        while j < len(prices):\n",
    "            # print(i,j,res)\n",
    "            if prices[j - 1] - prices[j] != 1:\n",
    "                res.append(j - i)\n",
    "                i = j\n",
    "            j += 1\n",
    "        if prices[len(prices) - 1] - prices[len(prices) - 2] == -1:\n",
    "            res.append(len(prices)  - i)\n",
    "        else:\n",
    "            res.append(1)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # for j in range(i+1, len(prices)):\n",
    "        #     if prices[j - 1] - prices[j] == 1:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         print(i,j)\n",
    "        #         res.append(j - i)\n",
    "        #         i = j\n",
    "\n",
    "        print(res)\n",
    "\n",
    "        count = 0\n",
    "        for e in res:\n",
    "            for i in range(1, e+1):\n",
    "                count += i\n",
    "        return count\n",
    "        # # print(prices)\n",
    "        # count = len(prices)\n",
    "\n",
    "        # # for i in range(1, len(prices)):\n",
    "        # #     if prices[i] - prices[i-1] == -1:\n",
    "        # #         count += 1\n",
    "\n",
    "        # # return count\n",
    "        # if len(prices) == 1:\n",
    "        #     return 1\n",
    "        # for l in range(2, len(prices) + 1):\n",
    "\n",
    "        #     for i in range(len(prices)):\n",
    "\n",
    "        #         if i + l < len(prices):\n",
    "        #             flag = False\n",
    "\n",
    "        #             for j in range(i + 1, i + l):\n",
    "        #                 print(\"a\", j, i,l, prices[j], prices[j-1])\n",
    "        #                 if prices[j] - prices[j-1] != -1:\n",
    "        #                     print(\"b\", j,i,l, prices[j - 1], prices[j])\n",
    "        #                     flag = True\n",
    "        #                     # break\n",
    "\n",
    "        #             if not flag:\n",
    "        #                 count += 1\n",
    "\n",
    "        # return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "\n",
    "        # res = []\n",
    "\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        count = 0\n",
    "        while j < len(prices):\n",
    "            # print(i,j,res)\n",
    "            if prices[j - 1] - prices[j] != 1:\n",
    "                # res.append(j - i)\n",
    "                e = j-i\n",
    "                count += (int)((1 + e) / 2 * e)\n",
    "                i = j\n",
    "            j += 1\n",
    "        if prices[len(prices) - 1] - prices[len(prices) - 2] == -1:\n",
    "            # res.append(len(prices)  - i)\n",
    "            e = len(prices)  - i\n",
    "            count += (int)((1 + e) / 2 * e)\n",
    "        else:\n",
    "            count += 1\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # for j in range(i+1, len(prices)):\n",
    "        #     if prices[j - 1] - prices[j] == 1:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         print(i,j)\n",
    "        #         res.append(j - i)\n",
    "        #         i = j\n",
    "\n",
    "        # print(res)\n",
    "\n",
    "        # count = 0\n",
    "        # for e in res:\n",
    "        #     # print((1 + e) / 2 * e)\n",
    "        #     count += (int)((1 + e) / 2 * e)\n",
    "        # # for e in res:\n",
    "        # #     for i in range(1, e+1):\n",
    "        # #         count += i\n",
    "        return count\n",
    "        # # print(prices)\n",
    "        # count = len(prices)\n",
    "\n",
    "        # # for i in range(1, len(prices)):\n",
    "        # #     if prices[i] - prices[i-1] == -1:\n",
    "        # #         count += 1\n",
    "\n",
    "        # # return count\n",
    "        # if len(prices) == 1:\n",
    "        #     return 1\n",
    "        # for l in range(2, len(prices) + 1):\n",
    "\n",
    "        #     for i in range(len(prices)):\n",
    "\n",
    "        #         if i + l < len(prices):\n",
    "        #             flag = False\n",
    "\n",
    "        #             for j in range(i + 1, i + l):\n",
    "        #                 print(\"a\", j, i,l, prices[j], prices[j-1])\n",
    "        #                 if prices[j] - prices[j-1] != -1:\n",
    "        #                     print(\"b\", j,i,l, prices[j - 1], prices[j])\n",
    "        #                     flag = True\n",
    "        #                     # break\n",
    "\n",
    "        #             if not flag:\n",
    "        #                 count += 1\n",
    "\n",
    "        # return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        cnt = 1\n",
    "        prev = 1\n",
    "        for i in range(1,n):\n",
    "            if prices[i]==prices[i-1]-1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            cnt += prev\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "\n",
    "        while j < len(prices):\n",
    "            # print(i,j,res)\n",
    "            if prices[j - 1] - prices[j] != 1:\n",
    "                res.append(j - i)\n",
    "                i = j\n",
    "            j += 1\n",
    "        if prices[len(prices) - 1] - prices[len(prices) - 2] == -1:\n",
    "            res.append(len(prices)  - i)\n",
    "        else:\n",
    "            res.append(1)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # for j in range(i+1, len(prices)):\n",
    "        #     if prices[j - 1] - prices[j] == 1:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         print(i,j)\n",
    "        #         res.append(j - i)\n",
    "        #         i = j\n",
    "\n",
    "        print(res)\n",
    "\n",
    "        count = 0\n",
    "        for e in res:\n",
    "            for i in range(1, e+1):\n",
    "                count += i\n",
    "        return count\n",
    "        # # print(prices)\n",
    "        # count = len(prices)\n",
    "\n",
    "        # # for i in range(1, len(prices)):\n",
    "        # #     if prices[i] - prices[i-1] == -1:\n",
    "        # #         count += 1\n",
    "\n",
    "        # # return count\n",
    "        # if len(prices) == 1:\n",
    "        #     return 1\n",
    "        # for l in range(2, len(prices) + 1):\n",
    "\n",
    "        #     for i in range(len(prices)):\n",
    "\n",
    "        #         if i + l < len(prices):\n",
    "        #             flag = False\n",
    "\n",
    "        #             for j in range(i + 1, i + l):\n",
    "        #                 print(\"a\", j, i,l, prices[j], prices[j-1])\n",
    "        #                 if prices[j] - prices[j-1] != -1:\n",
    "        #                     print(\"b\", j,i,l, prices[j - 1], prices[j])\n",
    "        #                     flag = True\n",
    "        #                     # break\n",
    "\n",
    "        #             if not flag:\n",
    "        #                 count += 1\n",
    "\n",
    "        # return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        r1=[]\n",
    "        l=len(prices)\n",
    "        c=1\n",
    "        for i in range(1,l):\n",
    "            if prices[i]==prices[i-1]-1:\n",
    "                c+=1\n",
    "            else:\n",
    "                r1.append(c*(c+1))\n",
    "                c=1\n",
    "        r1.append(c*(c+1))\n",
    "        return int(sum(r1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "\n",
    "        # res = []\n",
    "\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        count = 0\n",
    "        while j < len(prices):\n",
    "            # print(i,j,res)\n",
    "            if prices[j - 1] - prices[j] != 1:\n",
    "                # res.append(j - i)\n",
    "                e = j-i\n",
    "                count += (int)((1 + e) / 2 * e)\n",
    "                i = j\n",
    "            j += 1\n",
    "        if prices[len(prices) - 1] - prices[len(prices) - 2] == -1:\n",
    "            # res.append(len(prices)  - i)\n",
    "            e = len(prices)  - i\n",
    "            count += (int)((1 + e) / 2 * e)\n",
    "        else:\n",
    "            count += 1\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # for j in range(i+1, len(prices)):\n",
    "        #     if prices[j - 1] - prices[j] == 1:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         print(i,j)\n",
    "        #         res.append(j - i)\n",
    "        #         i = j\n",
    "\n",
    "        # print(res)\n",
    "\n",
    "        # count = 0\n",
    "        # for e in res:\n",
    "        #     # print((1 + e) / 2 * e)\n",
    "        #     count += (int)((1 + e) / 2 * e)\n",
    "        # # for e in res:\n",
    "        # #     for i in range(1, e+1):\n",
    "        # #         count += i\n",
    "        return count\n",
    "        # # print(prices)\n",
    "        # count = len(prices)\n",
    "\n",
    "        # # for i in range(1, len(prices)):\n",
    "        # #     if prices[i] - prices[i-1] == -1:\n",
    "        # #         count += 1\n",
    "\n",
    "        # # return count\n",
    "        # if len(prices) == 1:\n",
    "        #     return 1\n",
    "        # for l in range(2, len(prices) + 1):\n",
    "\n",
    "        #     for i in range(len(prices)):\n",
    "\n",
    "        #         if i + l < len(prices):\n",
    "        #             flag = False\n",
    "\n",
    "        #             for j in range(i + 1, i + l):\n",
    "        #                 print(\"a\", j, i,l, prices[j], prices[j-1])\n",
    "        #                 if prices[j] - prices[j-1] != -1:\n",
    "        #                     print(\"b\", j,i,l, prices[j - 1], prices[j])\n",
    "        #                     flag = True\n",
    "        #                     # break\n",
    "\n",
    "        #             if not flag:\n",
    "        #                 count += 1\n",
    "\n",
    "        # return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        r = 1\n",
    "        pre = prices[0]\n",
    "        lr = 0\n",
    "        def res(n):\n",
    "            return n*(n+1)//2\n",
    "\n",
    "        for num in prices[1:]:\n",
    "            if pre - num == 1:\n",
    "                r+=1\n",
    "            else:\n",
    "                # print(r)\n",
    "                lr+=res(r)\n",
    "                r = 1\n",
    "\n",
    "            pre = num\n",
    "        lr+=res(r)\n",
    "        return lr\n",
    "\n",
    "\n",
    "\n",
    "        # res = []\n",
    "\n",
    "        i = 0\n",
    "        j = i + 1\n",
    "        count = 0\n",
    "        while j < len(prices):\n",
    "            # print(i,j,res)\n",
    "            if prices[j - 1] - prices[j] != 1:\n",
    "                # res.append(j - i)\n",
    "                e = j-i\n",
    "                count += (int)((1 + e) / 2 * e)\n",
    "                i = j\n",
    "            j += 1\n",
    "        if prices[len(prices) - 1] - prices[len(prices) - 2] == -1:\n",
    "            # res.append(len(prices)  - i)\n",
    "            e = len(prices)  - i\n",
    "            count += (int)((1 + e) / 2 * e)\n",
    "        else:\n",
    "            count += 1\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # for j in range(i+1, len(prices)):\n",
    "        #     if prices[j - 1] - prices[j] == 1:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         print(i,j)\n",
    "        #         res.append(j - i)\n",
    "        #         i = j\n",
    "\n",
    "        # print(res)\n",
    "\n",
    "        # count = 0\n",
    "        # for e in res:\n",
    "        #     # print((1 + e) / 2 * e)\n",
    "        #     count += (int)((1 + e) / 2 * e)\n",
    "        # # for e in res:\n",
    "        # #     for i in range(1, e+1):\n",
    "        # #         count += i\n",
    "        return count\n",
    "        # # print(prices)\n",
    "        # count = len(prices)\n",
    "\n",
    "        # # for i in range(1, len(prices)):\n",
    "        # #     if prices[i] - prices[i-1] == -1:\n",
    "        # #         count += 1\n",
    "\n",
    "        # # return count\n",
    "        # if len(prices) == 1:\n",
    "        #     return 1\n",
    "        # for l in range(2, len(prices) + 1):\n",
    "\n",
    "        #     for i in range(len(prices)):\n",
    "\n",
    "        #         if i + l < len(prices):\n",
    "        #             flag = False\n",
    "\n",
    "        #             for j in range(i + 1, i + l):\n",
    "        #                 print(\"a\", j, i,l, prices[j], prices[j-1])\n",
    "        #                 if prices[j] - prices[j-1] != -1:\n",
    "        #                     print(\"b\", j,i,l, prices[j - 1], prices[j])\n",
    "        #                     flag = True\n",
    "        #                     # break\n",
    "\n",
    "        #             if not flag:\n",
    "        #                 count += 1\n",
    "\n",
    "        # return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        l, n, ans = 0, len(prices), 0\n",
    "        while l < n:\n",
    "            r = l + 1\n",
    "            while r < n and prices[r - 1] - prices[r] == 1: \n",
    "                r += 1            \n",
    "            #cnt = r - l + 1\n",
    "            #print(l, r, cnt)\n",
    "            ans += (r - l + 1) * (r - l) >> 1\n",
    "            l = r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        l = 1\n",
    "        ans = 0\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i] - prices[i+1] == 1:\n",
    "                l += 1\n",
    "            else:\n",
    "                ans += (l+1)*l//2\n",
    "                l = 1\n",
    "        return ans+(l+1)*l//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ans = 1\n",
    "        n = len(prices)\n",
    "        i = 0\n",
    "        k = 1\n",
    "        while i < n-1:\n",
    "            if prices[i] -1 ==prices[i+1]:\n",
    "                k+=1\n",
    "            else:\n",
    "                k=1\n",
    "            ans += k\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i<n:\n",
    "            j = i+1\n",
    "            while j<n and prices[j]-prices[j-1]==-1:\n",
    "                j +=1\n",
    "            tmp = j-i\n",
    "            if tmp==1:\n",
    "                ans +=1\n",
    "            else:\n",
    "                ans += int((tmp+1)*tmp/2)\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        cnt = 1\n",
    "        ans = 1\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i] == prices[i-1]-1:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt=1\n",
    "            ans+=cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        ret = 0\n",
    "        n = len(prices)\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i - 1] - 1:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ret += cnt * (cnt + 1) // 2\n",
    "                cnt = 1\n",
    "        ret += cnt * (cnt + 1) // 2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        pre=1000000\n",
    "        ans=[]\n",
    "        for num in prices:\n",
    "            if num!=pre-1:\n",
    "                ans.append(1)\n",
    "            else:#if num==pre-1:\n",
    "                ans[-1]+=1\n",
    "            pre=num\n",
    "        res=0\n",
    "        for num in ans:\n",
    "            res+=(1+num)*num//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        ans = i =0\n",
    "        while i < n:\n",
    "            s = i\n",
    "            i += 1\n",
    "            while i < n and prices[i] == prices[i-1] - 1:\n",
    "                i += 1\n",
    "            ans += (1 + i - s) * (i - s) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ret = 0\n",
    "        ans, t, length = [prices[0]], 1, 1\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i] + 1 == ans[-1]:\n",
    "                ans.append(prices[i])\n",
    "                length += 1\n",
    "                t += length\n",
    "            else:\n",
    "                ret += t\n",
    "                ans, t, length = [prices[i]], 1, 1\n",
    "        ret += t\n",
    "        return ret\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        p = prices\n",
    "        n = len(p)\n",
    "        k = 1\n",
    "        ans = 1\n",
    "        for i in range(1,n):\n",
    "            \n",
    "            if p[i] == p[i-1] -1:\n",
    "                k+=1\n",
    "            else:k=1\n",
    "            ans += k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        i,n=0,len(prices)\n",
    "        while i<n:\n",
    "            start = i\n",
    "            while i+1<n and prices[i]==prices[i+1]+1:\n",
    "                i+=1\n",
    "            res+=int((i-start+1)*(i-start+2)/2)\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            start = i \n",
    "            while i < n - 1 and prices[i] == prices[i + 1] + 1:\n",
    "                i += 1\n",
    "            x = i - start + 1\n",
    "            ans += int((1 + x) * x // 2)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ans=1\n",
    "        last=1\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]+1==prices[i-1]:\n",
    "                last+=1\n",
    "                ans+=last\n",
    "            else:\n",
    "                last=1\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        f = [1 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                f[i] = f[i-1] + 1\n",
    "        return sum(f)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        record=[]\n",
    "        seg=1\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]==prices[i-1]-1:\n",
    "                seg+=1\n",
    "            else:\n",
    "                record.append(seg)\n",
    "                seg=1\n",
    "        record.append(seg)\n",
    "        ans = sum([i*(i+1)//2 for i in record])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        # for idx, price in enumerate(prices):\n",
    "        idx = 0\n",
    "        cot_lst = []\n",
    "        if len(prices) == 1:\n",
    "            return 1\n",
    "        while idx < len(prices) - 1:\n",
    "            cot = 0\n",
    "            # print(idx)\n",
    "            while (prices[idx] - prices[idx + 1]) == 1:\n",
    "                cot += 1\n",
    "                idx += 1\n",
    "                print(idx)\n",
    "                if idx >= len(prices) - 1:\n",
    "                    break\n",
    "            cot_lst.append(cot)\n",
    "            idx += 1\n",
    "        result = 0\n",
    "        print(cot_lst)\n",
    "        for i in cot_lst:\n",
    "            if i != 0:\n",
    "                result += int((i * (i+1)) / 2)\n",
    "        return result + len(prices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        dp = [0] * len(prices)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] != prices[i-1] - 1:\n",
    "                dp[i] = 1\n",
    "            else: dp[i] = 1 + dp[i-1]\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        f = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if prices[i] - prices[i - 1] == -1:\n",
    "                f[i] = f[i - 1] + 1\n",
    "        return sum(f)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        i = 0 \n",
    "        res = 0\n",
    "        while i < len(prices):\n",
    "            start = i\n",
    "            \n",
    "            i += 1\n",
    "            while i < len(prices) and prices[i] == prices[i -1] -1:\n",
    "                i += 1\n",
    "\n",
    "            res += int((i - start)*(i - start + 1)/2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if prices[i-1] - prices[i] == 1:\n",
    "                dp[i] += dp[i-1]\n",
    "        return sum(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        c = 0\n",
    "        if len(prices) == 1:\n",
    "            return 1\n",
    "        i = 1\n",
    "        flag = 1\n",
    "        while i < len(prices):\n",
    "            if prices[i] - prices[i - 1] == -1:\n",
    "                flag += 1\n",
    "                i += 1\n",
    "                c += flag - 1\n",
    "            else:\n",
    "                flag = 1\n",
    "                i += 1\n",
    "        return c + len(prices)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        dp = [1]*len(prices)\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i-1]-prices[i]==1:\n",
    "                dp[i] = dp[i-1]+1\n",
    "\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        prices_len = len(prices)\n",
    "        ans = index = 0\n",
    "        while index< prices_len:\n",
    "            start = index+1\n",
    "            while start<prices_len and prices[start-1]-prices[start]==1:\n",
    "                start+=1\n",
    "            count = start-index\n",
    "            ans+= count*(count+1)//2\n",
    "            index =start\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, A: List[int]) -> int:\n",
    "        N = len(A)\n",
    "        dp = [ 1 ] * N\n",
    "        for i,x in enumerate(A):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            dp[i] = 1 if A[i-1] - A[i] != 1 else (dp[i-1] + 1)\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = l = 0\n",
    "        while l < n:\n",
    "            r = l + 1\n",
    "            while r < n and prices[r] - prices[r-1] == -1:\n",
    "                r += 1\n",
    "            m = r - l\n",
    "            res += m * (m + 1) // 2\n",
    "            l = r\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        ans =0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            start =i\n",
    "            i+=1\n",
    "            while i<n and prices[i]==prices[i-1]-1:\n",
    "                i+=1\n",
    "            ans += (i-start+1)*(i-start)//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [1] * n\n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                dp[i] += dp[i-1]\n",
    "            res += dp[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        # f[i] 表示第 i 个数时有多大长度的字串  \n",
    "        f = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if prices[i] - prices[i - 1] == -1:\n",
    "                f[i] = f[i - 1] + 1\n",
    "        return sum(f)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ans = n = len(prices)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and prices[i-1] - prices[i] == 1:\n",
    "                i += 1\n",
    "            count = i - start\n",
    "            ans += (count - 1)*count // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices) -> int:\n",
    "        n = len(prices)\n",
    "        ans = 1\n",
    "        pre = 1\n",
    "        for i in range(1, n):\n",
    "            if prices[i - 1] - prices[i] == 1:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            ans+=pre\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        ret = 0\n",
    "        l = 0\n",
    "        while l < n:\n",
    "            r = l+1\n",
    "            while r < n and prices[l] - prices[r] == (r - l):\n",
    "                r += 1\n",
    "            m = r-l\n",
    "            ret += (m+1) * m // 2\n",
    "            l = r\n",
    "        return ret\n",
    "        # return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ret = f = 1\n",
    "        for i in range(1, len(prices)):\n",
    "            f = f + 1 if prices[i-1] - prices[i] == 1 else 1\n",
    "            ret += f\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 0\n",
    "        ans = n\n",
    "        for i in range(1,n):\n",
    "            if prices[i-1] - prices[i] == 1:\n",
    "                res += 1\n",
    "            else:\n",
    "                ans += (res*(res+1))//2\n",
    "                res = 0\n",
    "        ans += (res*(res+1))//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        i, ans, n = 0, 0, len(prices)\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and prices[i] - prices[j] == j - i:\n",
    "                j += 1\n",
    "            cnt = j - i\n",
    "            ans += cnt * (cnt + 1) // 2\n",
    "            i = j\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ans, n, i = 0, len(prices), 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and prices[i] + 1 == prices[i - 1]:\n",
    "                i += 1\n",
    "            ans += (i - start) * (i - start + 1) // 2\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ans=0\n",
    "        p=-1\n",
    "        c=0\n",
    "        for x in prices:\n",
    "            if x==p-1:\n",
    "                c+=1\n",
    "            else:\n",
    "                c=1\n",
    "            ans+=c\n",
    "            p=x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        while right < n:\n",
    "            if left == right:\n",
    "                right += 1\n",
    "                res += 1\n",
    "                continue\n",
    "\n",
    "            if prices[right] - prices[right - 1] == -1:\n",
    "                res += right - left + 1\n",
    "                right += 1\n",
    "            else:\n",
    "                left = right\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices) -> int:\n",
    "        n = len(prices)\n",
    "        ans = 1\n",
    "        pre = 1\n",
    "        for i in range(1, n):\n",
    "            if prices[i - 1] - prices[i] == 1:\n",
    "                ans += pre + 1\n",
    "                pre = pre + 1\n",
    "            else:\n",
    "                ans += 1\n",
    "                pre = 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        def arr(left, right):\n",
    "            return int((right - left + 2) * (right - left + 1) / 2)\n",
    "        if len(prices) == 1:\n",
    "            return 1\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] - prices[i - 1] == -1:\n",
    "                right = i\n",
    "            else:\n",
    "                ans += arr(left, right)\n",
    "                left = i\n",
    "                right = i\n",
    "        return ans + arr(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = n\n",
    "        i = 1\n",
    "        while i<n:\n",
    "            if prices[i]==prices[i-1]-1:\n",
    "                left = i-1\n",
    "                while i<n and prices[i]==prices[i-1]-1:\n",
    "                    i+=1\n",
    "                i-=1\n",
    "                k = i-left+1\n",
    "                res += (k*(k-1)//2)\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        # dp = [1] * n\n",
    "        res = 0\n",
    "        left = right = 0\n",
    "        while right < n :\n",
    "            if left == right:\n",
    "                res += 1\n",
    "                right += 1\n",
    "                continue\n",
    "            if prices[right] == prices[right-1] - 1:\n",
    "                res += right - left + 1\n",
    "                right += 1\n",
    "            else:\n",
    "                left = right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 1   # 平滑下降阶段的总数，初值为 dp[0]\n",
    "        prev = 1   # 上一个元素为结尾的平滑下降阶段的总数，初值为 dp[0]\n",
    "        # 从 1 开始遍历数组，按照递推式更新 prev 以及总数 res\n",
    "        for i in range(1, n):\n",
    "            if prices[i] == prices[i-1] - 1:\n",
    "                prev += 1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res += prev\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDescentPeriods(self, prices) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if prices[i - 1] - prices[i] == 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "        return sum(dp)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
